package com.mj.HashMap;

//import com.mj.Map.tree.BinaryTree;

import java.util.Comparator;
import java.util.LinkedList;
import java.util.Queue;

/**
 * @Author: LDeng
 * @Date: 2021-03-10 16:04
 */
public class TreeMap<K,V> implements Map<K,V> {

    private static final boolean RED = false;
    private static final boolean BLACK = true;
    
    private int size;
    private Node<K,V> root;//根节点属性

    private Comparator<K> comparator;


    public TreeMap() {//提供空构造 ， 让使用者可以不传比较器而使用默认的比较器
        this(null);
    }

    public TreeMap(Comparator<K> comparator) {
        this.comparator = comparator;
    }

    public int size() {
        return size;
    }

    public boolean isEmpty() {
        return size == 0;
    }

    public void clear() {
        root=null;
        size=0;
    }

    private void keyNotNullCheck(K key) {
        if (key == null) {
            throw new IllegalArgumentException("element must not be null");
        }
    }

    @Override
    public V put(K key, V value) {
        keyNotNullCheck(key);
        if (root == null) {//添加第一个节点
            root = new Node<>(key,value, null);
            size++;
            afterPut(root);
            return null;
        }
        //添加的不是第一个节点
        //找要插入元素的到父节点
       Node<K,V> parent = root;
      Node<K,V> node = root;
        int comp = 0;
        while (node != null) {
            comp = compare(key, node.key);
            parent = node;
            if (comp > 0) {//element>node.element 传进来的元素大于节点元素
                node = node.right;
            } else if (comp < 0) {//
                node = node.left;
            } else {//相等, 直接返回
                node.key = key;//使用传进来的元素覆盖原来的元素
                V oldValue=node.value;
                node.value=value;
                return oldValue;
            }
        }
        // 插入到父节点的左边还是右边
        Node<K,V> newNode = new Node<>(key,value, parent);
        if (comp > 0) {
            parent.right = newNode;
        } else {
            parent.left = newNode;
        }
        size++;
        afterPut(newNode);
        return null;
    }



    @Override
    public V get(K key) {
        Node<K,V> node=getNodeByKey(key);
        return node!=null?node.value:null;
    }
    
    

    @Override
    public V remove(K key) {
        return remove(getNodeByKey(key));
    }

    @Override
    public boolean containsKey(K key) {
        return getNodeByKey(key)!=null;
    }

    @Override//遍历－层序
    public boolean containsValue(V value) {
        if(root==null) return false;
        Queue<Node<K,V>> queue=new LinkedList<>();
        queue.offer(root);
        while(!queue.isEmpty()){
            Node<K, V> node = queue.poll();
            if(valueEquals(node.value,value)) return true;
            if(node.left!=null){
                queue.offer(node.left);
            }
            if(node.right!=null){
                queue.offer(node.right);
            }
        }
        return false;
    }

    @Override//遍历-中序
    public void traversal(Visitor<K, V> visitor) {
        //中序遍历， 按照key从小到大　
        if(visitor==null) return;
        traversal(root,visitor);
    }

    private void traversal(Node<K,V> node,Visitor<K,V> visitor){
        if(node==null || visitor.stop) return;
        traversal(node.left,visitor);
        if(visitor.stop) return;
        visitor.visit(node.key,node.value);
        traversal(node.right,visitor);
    }

    private boolean valueEquals(V v1,V v2){
        return v1==null?v2==null:v1.equals(v2);
    }

    private static class Node<K,V>{
        K key;
        V value;
        boolean color=RED;
        Node<K,V> left;
        Node<K,V> right;
        Node<K,V> parent;

        public Node(K key,V value, Node<K,V> parent) {//构造
            this.key = key;
            this.value=value;
            this.parent = parent;
        }

        public boolean isLeaf() {
            return left == null && right == null;
        }

        public boolean hasTwoChildren() {
            return left != null && right != null;
        }

        public boolean isLeftChind(){
            return parent!=null && this==parent.left;
        }
        public boolean isRightChild(){
            return parent!=null && this==parent.right;
        }

        public Node<K,V> sibling(){
            if(isLeftChind()){
                return parent.right;
            }
            if(isRightChild()){
                return parent.left;
            }
            //没有左也没有右，父节点为空， 返回空兄弟节点
            return null;
        }
    }


    //节点染色并返回染色后的节点
    private Node<K,V> color(Node<K,V> node, boolean color) {
        if (node == null) return node;
        node.color = color;
        return node;
    }
    //将节点染成红色并返回
    private Node<K,V> red(Node<K,V> node){
        return color(node,RED);
    }

    //将节点染成黑色并返回
    private Node<K,V> black(Node<K,V> node){
        return color(node,BLACK);
    }

    //取出当前节点颜色
    private boolean colorOf(Node<K,V> node){
        //空节点返回黑色，其他根据实际是什么颜色就返回什么颜色
        return node==null?BLACK:node.color;
    }

    //判断节点是否为黑色
    private boolean isBlack(Node<K,V> node){
        return colorOf(node)==BLACK;
    }
    //判断节点是否为红色
    private boolean isRed(Node<K,V> node){
        return colorOf(node)==RED;
    }


    private void rotateLeft(Node<K,V> grand){//节点左旋转
        Node<K,V> p=grand.right;
        Node<K,V> child=p.left;
        //更新g的右节点和p的左节点
        grand.right=child;
        p.left=grand;

        afterRotate(grand,p,child);
    }

    private void rotateRight(Node<K,V> grand){
        Node<K,V> p=grand.left;
        Node<K,V> child=p.right;
        grand.left=child;
        p.right=grand;
        afterRotate(grand,p,child);
    }

    private void afterRotate(Node<K,V> grand, Node<K,V> p, Node<K,V> child) {
        //更新p,g 的parent属性( 双向 )
        p.parent = grand.parent;
        if (grand.isLeftChind()) {//g是父节点的左节点
            grand.parent.left = p;
        } else if (grand.isRightChild()) {//g是父节点的右节点
            grand.parent.right = p;
        } else {//父节点是空，g是根节点
            root = p;//根节点指向p
        }
        //更新p左子节点的parent
        if (child != null) {
            child.parent = grand;
        }
        //更新g的parent
        grand.parent = p;
    }


    // 返回值=0 e1,e2相等，
    // 返回值>0 e1>e2
    // 返回值<0 e1<e2
    private int compare(K k1, K k2) {//上面对泛型进行了约束， 传进来的对象必然是实现了Comparable接口的对象， 可比较
        if (comparator != null) {
            return comparator.compare(k1, k2);
        }
        return ((Comparable<K>) k1).compareTo(k2);
    }

    private void afterPut(Node<K,V> node){
        Node<K,V> parent=node.parent;
        //如果添加的是根节点, 或者上溢到根节点（递归退出条件）
        if(parent==null){
            black(node);
            return;
        }
        //如果父节点是黑色，直接返回
        if(isBlack(parent)) return;
        Node<K,V> uncle=parent.sibling();
        Node<K,V> grand=parent.parent;
        //叔父节点是红色
        if(isRed(uncle)){
            black(parent);
            black(uncle);
            Node<K,V> grand_red= red(grand);//祖父节点染成红色，上溢并递归
            afterPut(grand_red);
            return;
        }
        //叔父节点不是红色
        if(parent.isLeftChind()){//L
            red(grand);
            if(node.isLeftChind()){//LL
                black(parent);
            }else{//LR
                black(node);
                rotateLeft(parent);
            }
            rotateRight(grand);
        }else{//R
            red(grand);
            if(node.isLeftChind()){//RL
                black(node);
                rotateRight(parent);
            }else{//RR
                black(parent);
            }
            rotateLeft(grand);
        }
    }
    

    //通过Key查找节点的方法
    private Node<K,V> getNodeByKey(K key) {
        Node<K,V> node = root;
        while (node != null) {
            int compar = compare(key, node.key);
            if (compar == 0) return node;
            if (compar > 0) {
                node = node.right;
            } else {
                node = node.left;
            }
        }
        return null;
    }

    //对内使用删除节点的接口
    private V remove(Node<K,V> node) { //后继节点覆盖被删除节点
        if (node == null) return null;
        size--;
        V oldValue=node.value;
        if (node.hasTwoChildren()) {//度为2, 使用被删除节点的前驱或者后继节点取代被删除的节点
            //找到后继节点
            Node<K,V> s = successor(node);
            //用后继节点的值覆盖node节点的值
            node.key = s.key;
            node.value = s.value;
            //删除后继节点
            node = s;//将node指向s节点， 为了下面统一删除度为1 和 0 的节点， 这里只做一个指向
        }
        //删除node节点（能执行到这里， node的度必然是1或者0）
        Node<K,V> replacement = node.left != null ? node.left : node.right;
        if (replacement != null) {//node 度为1的节点
            //更改node的parent
            replacement.parent = node.parent;
            //更改parent的left,right
            if (node.parent == null) {//node 度为1，并且是根节点
                root = replacement;
            } else if (node == node.parent.left) {
                node.parent.left = replacement;
            } else {//node == node.parent.right
                node.parent.right = replacement;
            }
            //删除节点后的处理（恢复平衡）,
            //这里不需要担心node被销毁， 因为他自生还有指针指向parent
            afterRemove(node,replacement);

        } else if (node == root) {//node度为0=>叶子节点,并且只有一个根节点
            root = null;
            //删除节点后的处理（恢复平衡）
            afterRemove(node,null);

        } else {//node是叶子节点，但不是根节点
            if (node == node.parent.left) {//node在父节点的左边
                node.parent.left = null;
            } else {//node在父节点的右边
                node.parent.right = null;
            }
            //删除节点后的处理（恢复平衡）
            afterRemove(node,null);
        }
        return oldValue;
    }

    //后续节点， 中序遍历时的前一个节点（左子树的最后一个节点）
    protected Node<K,V> successor(Node<K,V> node) {
        if (node == null) return null;
        //1 ，右边不为空，前驱节点在右子树中(right.left.left.....)
        Node<K,V> p = node.right;
        if (p != null) {
            p = node.right;
            while (p.left != null) {
                p = p.left;
            }
            return p;
        }
        //从父节点，祖父节点。。。中寻找前驱节点,
        // 父节点不为空， 并且本节点在父节点的左子树中
        while (node.parent != null && node == node.parent.right) {
            node = node.parent;
        }

        //node.parent==null ==>返回空（node.parent）
        //node==node.parent.right ==> 本节点的parent节点就是前驱
        return node.parent;
    }


    protected void afterRemove(Node<K,V> node, Node<K,V> replacement) {
        //如果删除的是红色节点， 直接删除即可
        if(isRed(node)) return;

        //用以取代删除节点的节点是红色
        if(isRed(replacement)){
            black(replacement);
            return;
        }
        Node<K,V> parent= node.parent;
        //删除的叶子节点是根节点， 直接返回
        if(parent==null) return;
        //能来到这里表示删除的是黑色叶子节点
        //Node<E> sibling=node.sibling();
        //判断被删除的节点是左边还是右边(用parent.left是否是空来判断)
        //如果parent.left是空， 则删除的节点在左边，那么sibling在必然在右边， 反之 sibling在左边
        //递归的情况，跟parent的连线还在，所有可以用isLeftChild()来判断
        boolean left=parent.left==null||node.isLeftChind();
        Node<K,V> sibling=left?parent.right:parent.left;
        if(left){//被删除的节点在左边，兄弟节点在右边
            if(isRed(sibling)){//兄弟节点是红色=>转化成兄弟节点是黑色，复用
                black(sibling);
                red(parent);
                rotateLeft(parent);
                //更换兄弟
                sibling=parent.right;//sibling指向parent.left（黑色）
            }
            //现在可以统一处理sibling是黑色的情况
            if(isBlack(sibling.left)&&isBlack(sibling.right)){//黑黑，没有红色子节点可以借出
                //判断父节点颜色
                boolean parentBlack=isBlack(parent);
                black(parent);
                red(sibling);
                if(parentBlack){
                    afterRemove(parent,null);
                }
            }else {//VS 黑红+红黑+红红, 兄弟节点至少有一个红色节点可以借出
                //向兄弟节点借元素， 三种情况
                //    红节点在兄弟节点右边 兄弟节点左旋+父节点右旋，
                //    红节点在兄弟节点左边             父节点右旋
                //    红节点两边走有，                 父节点右旋
                //这里先把第一种特殊处理一下， 然后统一代码左父节点右旋
                if (isBlack(sibling.right)) {//红节点在右边，先旋转兄弟节点,在将sibling指向父节点的左边
                    rotateRight(sibling);
                    sibling = parent.right;//sibling指向
                }
                //拿到被删除节点父节点的颜色，给兄弟染色
                color(sibling, colorOf(parent));
                black(sibling.right);
                black(parent);
                rotateLeft(parent);
            }

        }else{//被删除的节点在右边，兄弟节点在左边（对称处理）
            if(isRed(sibling)){//兄弟节点是红色=>转化成兄弟节点是黑色，复用
                black(sibling);
                red(parent);
                rotateRight(parent);
                //更换兄弟
                sibling=parent.left;//sibling指向parent.left（黑色）
            }
            //现在可以统一处理sibling是黑色的情况
            if(isBlack(sibling.left)&&isBlack(sibling.right)){//黑黑，没有红色子节点可以借出
                //判断父节点颜色
                boolean parentBlack=isBlack(parent);
                black(parent);
                red(sibling);
                if(parentBlack){
                    afterRemove(parent,null);
                }
            }else{//VS 黑红+红黑+红红, 兄弟节点至少有一个红色节点可以借出
                //向兄弟节点借元素， 三种情况
                //    红节点在兄弟节点右边 兄弟节点左旋+父节点右旋，
                //    红节点在兄弟节点左边             父节点右旋
                //    红节点两边走有，                 父节点右旋
                //这里先把第一种特殊处理一下， 然后统一代码左父节点右旋
                if(isBlack(sibling.left)){//红节点在右边，先旋转兄弟节点,在将sibling指向父节点的左边
                    rotateLeft(sibling);
                    sibling=parent.left;//sibling指向
                }
                //拿到被删除节点父节点的颜色，给兄弟染色
                color(sibling,colorOf(parent));
                black(sibling.left);
                black(parent);
                rotateRight(parent);
            }
        }
    }
}
